import java.util.ArrayList;
import java.util.List;

public class FullDuplexModel {

  private static double augment(final double the_flow, final List<Edge> the_path) {
    double b = bottleneck(the_path);
    for (Edge e : the_path) {
      if (e.my_capacity - e.my_flow >= 0) {
        e.my_flow += b;
      } else {
        e.my_flow -= b;
      }
    }
    return the_flow + b;
  }

  private static double bottleneck(final List<Edge> the_path) {
    double b = Double.MAX_VALUE;
    for (Edge e : the_path) {
      double residual_flow = e.my_capacity - e.my_flow;
      if (residual_flow < b) {
        b = residual_flow;
      }
    }
    return b;
  }

  private static double maxFlow(final Network the_graph) {
    // prep graph
    double f = 0.0;
    for (Edge e : the_graph.my_forward_edges) {
      e.my_flow = 0.0;
    }
    for (Node n : the_graph.my_nodes) {
      n.discovered = false;
      n.explored = false;
    }
    Network graph = the_graph;

    // algorithm
    List<Edge> path = findPath(graph, graph.my_s, new ArrayList<Edge>());
    while (path != null) {
      f = augment(f, path);
      path.clear();
      // System.out.println("Augmented flow.  Current flow is " + f + ".");
      // make residual graph
      List<Edge> residual_fedges = new ArrayList<Edge>();
      List<Edge> residual_bedges = new ArrayList<Edge>();
      for (Edge e : graph.my_forward_edges) {
        if (e.my_flow < e.my_capacity) {
          residual_fedges.add(new Edge(0, e.my_capacity - e.my_flow, e.my_u,
              e.my_v));
        }
      }
      for (Edge e : the_graph.my_forward_edges) {
        if (e.my_flow > 0) {
          residual_bedges.add(new Edge(0, e.my_flow, e.my_v, e.my_u));
        }
      }
      Node s = graph.my_s;
      Node t = graph.my_t;
      graph = new Network(graph.my_nodes, residual_fedges, residual_bedges);
      graph.my_s = s;
      graph.my_t = t;
      path = findPath(graph, graph.my_s, path);
    }
    return f;
  }

  private static List<Edge> findPath(final Network the_graph, final Node v,
      final List<Edge> the_path) {
    v.discovered = true;
    if (v == the_graph.my_t) {
      return the_path;
    }
    for (Edge e : findOut(the_graph, v)) {
      if (e.backedge == false && e.discovered == false) {
        Node w = e.my_v;
        if (w.explored == false && e.my_flow < e.my_capacity) {
          e.discovered = true;
          the_path.add(e);
          List<Edge> result = findPath(the_graph, w, the_path);
          if (result != null) {
            return result;
          }
        } else {
          e.backedge = true;
        }
      }
    }
    v.explored = true;
    return null;
  }

  private static List<Edge> findOut(final Network the_graph, final Node the_v) {
    List<Edge> result = new ArrayList<Edge>();
    for (Edge e : the_graph.my_forward_edges) {
      if (e.my_u == the_v) {
        result.add(e);
      }
    }
    for (Edge e : the_graph.my_backward_edges) {
      if (e.my_u == the_v) {
        result.add(e);
      }
    }
    return result;
  }

  public static void main(String[] args) {
    // setup
    List<Node> nodes = new ArrayList<Node>();
    Node base = new Node();
    Node su1 = new Node();
    Node su2 = new Node();
    Node ch1_in = new Node();
    Node ch2_in = new Node();
    Node ch3_in = new Node();
    Node ch4_in = new Node();
    Node ch1_out = new Node();
    Node ch2_out = new Node();
    Node ch3_out = new Node();
    Node ch4_out = new Node();
    Node virtual_sink = new Node();
    nodes.add(base);
    nodes.add(su1);
    nodes.add(su2);
    nodes.add(ch1_in);
    nodes.add(ch2_in);
    nodes.add(ch3_in);
    nodes.add(ch4_in);
    nodes.add(ch1_out);
    nodes.add(ch2_out);
    nodes.add(ch3_out);
    nodes.add(ch4_out);
    nodes.add(virtual_sink);

    List<Edge> edges = new ArrayList<Edge>();
    edges.add(new Edge(0, 1.0, ch1_in, ch1_out));
    edges.add(new Edge(0, 1.0, ch2_in, ch2_out));
    edges.add(new Edge(0, 1.0, ch3_in, ch3_out));
    edges.add(new Edge(0, 1.0, ch4_in, ch4_out));
    edges.add(new Edge(0, 1.0, base, ch1_in));
    edges.add(new Edge(0, 1.0, su1, ch1_in));
    edges.add(new Edge(0, 1.0, ch1_out, base));
    edges.add(new Edge(0, 1.0, ch1_out, su1));
    edges.add(new Edge(0, 1.0, base, ch2_in));
    edges.add(new Edge(0, 1.0, su2, ch2_in));
    edges.add(new Edge(0, 1.0, ch2_out, base));
    edges.add(new Edge(0, 1.0, ch2_out, su2));
    edges.add(new Edge(0, 1.0, su1, ch3_in));
    edges.add(new Edge(0, 1.0, su2, ch3_in));
    edges.add(new Edge(0, 1.0, ch3_out, su1));
    edges.add(new Edge(0, 1.0, ch3_out, su2));
    edges.add(new Edge(0, 1.0, base, ch4_in));
    edges.add(new Edge(0, 1.0, su1, ch4_in));
    edges.add(new Edge(0, 1.0, ch4_out, base));
    edges.add(new Edge(0, 1.0, ch4_out, su1));

    edges.add(new Edge(0, 2.3, su1, virtual_sink));
    edges.add(new Edge(0, 0.7, su2, virtual_sink));

    Network graph = new Network(nodes, edges, new ArrayList<Edge>());
    graph.my_s = base;
    graph.my_t = virtual_sink;

    System.out.println("Setup complete.");

    // algorithm
    // double startTime = System.nanoTime();
    // double maxThroughput = maxFlow(graph);
    // double endTime = System.nanoTime();
    // System.out.println("The maximum flow found is " + maxThroughput + ".");
    // System.out.println("The algorithm took " + (endTime - startTime) +
    // "nanoseconds.");

    double minimum = Double.MAX_VALUE;
    double running_total = 0.0;
    double maximum = Double.MIN_VALUE;
    for (int i = 0; i < 100; i++) {
      double startTime = System.nanoTime();
      double maxThroughput = maxFlow(graph);
      double endTime = System.nanoTime();
      double result = endTime - startTime;
      if (result < minimum) {
        minimum = result;
      } else if (result > maximum) {
        maximum = result;
      }
      running_total += result;
    }
    System.out.println("100 runs completed. Minimum: " + minimum + ", mean: "
        + (running_total / 100) + ", maximum: " + maximum + ".");
  }
}
